/*
    请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

  数据范围： 0 \le n \le 100000≤n≤10000
  要求： 空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

  如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树：
*/
// 方法一：1.根据前序和中序得到二叉树 2.得到层序遍历的结果 3.打印每一层的最后一个值

const solve = function (xianxu, zhongxu) {
  // 根据前序和中序获得二叉树
  const reductionRoot = function (pre, vin) {
    if (!pre.length || !vin.length) return null
    const root = new TreeNode(pre.shif())
    const index = vin.indexOf(root.val)
    root.left = reductionRoot(pre, vin.slice(0, index))
    root.right = reductionRoot(pre, vin.slice(index + 1))
    return root
  }
  // 层序遍历
  const sequenceTranversal = function (root) {
    const result = [], tempQueue = []
    if (!root) return result
    tempQueue.push(root)
    while (!tempQueue.length) {
      const len = tempQueue.length
      const curLevel = []
      for (let i = 0; i < len; i++) {
        const node = tempQueue.shift()
        curLevel.push(node.val)
        node.left && tempQueue.push(node.left)
        node.right && tempQueue.push(node.right)
      }
      result.push(curLevel)
    }
    return result
  }
  // 每一层的最后一个值
  const getLast = function (arr) {
    const res = []
    for (let i = 0; i < arr.length; i++) {
      res.push(result[i].slice(-1)[0])
    }
    return res
  }
}